import java.util.ArrayList;

import java.util.List;
public class OPTPageReplacement {

    public static void main(String[] args) {

        int[] pageRequests = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1};

        int numFrames = 4;
        List<Integer> frames = new ArrayList<>();

        int pageFaults = 0;
        for (int i = 0; i < pageRequests.length; i++) {

            int page = pageRequests[i];

            boolean pageFound = false;

            for (int framePage : frames) {

                if (framePage == page) {

                    pageFound = true;

                    break;

                }

            }
            if (!pageFound) {

                if (frames.size() < numFrames) {

                    frames.add(page);

                    System.out.println("页面 " + page + " 被添加到帧中. 当前帧: " + frames);

                } else {

                    int farthestIndexToReplace = -1;

                    int farthestFutureUse = Integer.MAX_VALUE;



                    for (int j = 0; j < frames.size(); j++) {

                        int framePage = frames.get(j);

                        int nextUseIndex = -1;

                        for (int k = i + 1; k < pageRequests.length; k++) {

                            if (pageRequests[k] == framePage) {

                                nextUseIndex = k;

                                break;

                            }

                        }
                        if (nextUseIndex != -1 && nextUseIndex > i && (nextUseIndex - i) > farthestFutureUse) {

                            farthestFutureUse = nextUseIndex - i;

                            farthestIndexToReplace = j;
                        }
                    }
                    if (farthestIndexToReplace != -1) {

                        int evictedPage = frames.remove(farthestIndexToReplace);

                        frames.add(page);

                        System.out.println("页面 " + evictedPage + " 被替换为 " + page + ". 当前帧: " + frames);

                    } else {

                        // This should not happen in a correctly implemented OPT algorithm,

                        // as we always find a page to replace based on future use.

                        // But just in case of a bug or edge case, we'll add the page and log it.

                        frames.add(page);

                        System.out.println("Unexpected situation: Added " + page + " without replacement. Current frames: " + frames);

                    }

                }

                pageFaults++;

            } else {

                System.out.println("页面 " + page + " 已在帧中. 当前帧: " + frames);

            }

        }
        System.out.println("\n最终帧内容: " + frames);

        System.out.println("OPT页面中断次数：" + pageFaults);

        // 页面命中率计算

        double pageHitRate = (double)(pageRequests.length - pageFaults) / pageRequests.length;

        System.out.println("OPT页面命中率：" + (pageHitRate * 100) + "%");

    }

}